﻿#define _CRT_SECURE_NO_WARNINGS 1
@[Toc](leetcode)
# 6. 和为s的两个数字
[题目](https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/)

```cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        //排序+双指针
        sort(price.begin(), price.end());
        int left = 0, right = price.size() - 1;
        while (left < right)
        {
            int ret = price[left] + price[right];
            if (ret > target)
            {
                right--;
            }
            else if (ret < target)
            {
                left++;
            }
            else
            {
                //隐式类型转换
                return { price[left],price[right] };
            }
        }
        return {};
    }
};
```

# 7.三数之和
[三数之和](https://leetcode.cn/problems/1fGaJU/description/)

```cpp
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //延续上一题的做法，不过只是target会改变
        //复杂的是这里需要去重也就是三元组之间没有交集（参考集合）
        sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int n = nums.size();
        //i++不能在这里，否则会跳过部分元素
        //三元组，因此i最多等于n-3
        for (int i = 0; i < n - 2;)
        {
            //对于一个已经排好序的数组来说，正整数不需要固定了，因为三数之和一定大于0
            if (nums[i] > 0)
                break;
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target)
                    right--;
                else if (sum < target)
                    left++;
                else
                {
                    vv.push_back({ nums[left],nums[right],nums[i] });
                    left++;
                    right--;
                    //去重,防止越界如[0,0,0,0,0,0]left会减到-1
                    while (left < right && nums[left] == nums[left - 1])left++;
                    while (left < right && nums[right] == nums[right + 1])right--;
                }
            }
            i++;
            while (i < n - 2 && nums[i] == nums[i - 1])i++;
        }
        return vv;
    }
};

```

# 8. 四数之和
[四数之和](https://leetcode.cn/problems/4sum/description/)

```cpp
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //延续上一题，不过在此之上要多固定一个
        sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int n = nums.size();
        for (int i = 0; i < n - 3;)
        {
            for (int j = i + 1; j < n - 2;)
            {
                int left = j + 1, right = n - 1;
                while (left < right)
                {
                    //数据太大了整形存不下来，[1000000000,1000000000,1000000000,1000000000]，用long long
                    //可以先去减target，nums[i]-(long long)这样的话会进行提升做64位的计算，放到后面也会存储不下来
                    long long aim = nums[i] - (long long)target + nums[j] + nums[right] + nums[left];
                    if (aim < 0)
                        left++;
                    else if (aim > 0)
                        right--;
                    else
                    {
                        vv.push_back({ nums[left],nums[right],nums[i],nums[j] });
                        left++;
                        right--;
                        //去重
                        while (left < right && nums[left] == nums[left - 1])left++;
                        while (left < right && nums[right] == nums[right + 1])right--;
                    }
                }
                j++;
                while (j < n - 2 && nums[j] == nums[j - 1])j++;
            }
            i++;
            while (i < n - 3 && nums[i] == nums[i - 1])i++;
        }
        return vv;
    }
};
```

# 9. 长度最小的子数组
[长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum/description/)
```cpp
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //滑动窗口问题
        //暴力求解:枚举+我们可以通过左下标和右下标划分子数组+遍历子数组求和，O（n^3）
        //滑动窗口是基于“同向双指针”的思想，也就是左右指针朝一个方向移动这是基于求和的单调性
        int left = 0, right = -1, n = nums.size(), sum = 0, len = 100001;
        for (int left = 0, right = 0; right < n; right++)
        {
            //循环进或者循环出，不要用if来判断
            sum += nums[right]; // 进窗⼝ 
            while (sum >= target) // 判断 
            {
                len = len > right - left + 1 ? right - left + 1 : len;// 更新结果 
                sum -= nums[left++]; // 出窗⼝ 
            }
        }
        //注意len最大为100000，可能整个数组求和都小于target，此时判断len是否等于100001来判断村子不符合条件的子数组
        return len == 100001 ? 0 : len;
    }
};
```

# 10. 无重复字符的最长子串
[无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/)

```cpp
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //滑动窗口问题
        //我们需要一个哈希表来映射相同元素以便可以去重
        //对于一个重复子串，我们很容易想到除非我们跳过重复元素，否则重复子串的子串一定是减少的
        //通过整形数组实现哈希表
        int n = s.size();
        int len = 0;
        // 创建⼀个哈希表，统计频次
        int hash[96] = { 0 };
        for (int left = 0, right = 0; right < n; right++)
        {
            //映射
            char gap = 31;
            // 寻找结束为⽌ 
            hash[s[right] - 31]++; // 统计字符出现的频次 
            while (hash[s[right] - 31] > 1) // 如果出现重复的
            {
                hash[s[left] - 31]--;
                left++;
            }
            // 如果没有重复，就更新 ret 
            len = len > right - left + 1 ? len : right - left + 1;
        }
        return len;
    }
};